群・環・体入門 ：Section 1 整数
AC.icon 定理1.1 加法の簡単化
両辺に加える操作していいんやろか....
まあ、証明はすぐできるだろうけど
$ bから$ cを直接変形する
$ 0aの$ 0とは、ここでは加法単位元以上の意味を持たない。
そのため、加法と単位元の関連を示す規則（$ x + (-x) = 0, $ a + 0 = 0）が重要になる
上の内容から、$ 0aを評価するためには加法単位元と乗法の関連を理解する必要がある。 分配法則は加法と乗法の単位元を示した唯一の法則である。 $ x + (-x) = 0の方から解析してみた
....？？？
解けぬぇ.......悔しい.......appbird.icon
なぜ解けなかったのだろうか？
$ 0a = 0の証明に、なぜ$ 0 = 0 + aが有効だと気づけるだろうか？
本来の目的を見失って探索してしまった感じがある
$ x + (-x) = 0で突っかかったときに、その困難をどう言語化するのかな
$ -(ax) = -(a)xを示す必要があるんだけど、これを示すのに$ 0x = 0が必要
多分これは避けられない
逆元の定義（原理）に基づいてこれを示すと考えた以上
ある演算結果が0になることを示した定理が必須になるのでやっぱりここが必要になる可能性は高い
と思うと、やはりこの方針は避けたい
だから、$ 0 + a = 0の方に着目するべきだった
このように困難があることをまともに捉えなかったのが問題な気がするなあ
AC.icon 定理 1.3 逆限の基本定理
(4)は(3)を再利用すれば逆元の記号をなかったことにできる。
AC.icon 定理 1.4 式の簡単化（乗法）
$ ab = acを変形して因数分解
ちょっと迷った
$ bから変形して直接示すのは難しそうかな
$ aの条件をうまく活用できない...って思ったけど、できるか
$ b - c = b - c + 0 = b - c + ab - ac =
$ a\neq 0の条件を活かせるのはどこかと考えると、IXを使いたくなるので、そこに着目
$ b \; | \; a $ b devides $ a
$ a|bかつ$ b|aなら$ a = \pm b
定義に基づいて変形
最大って扱いにくくない...？？？
最小も扱いにくいな
定理で示す時は....背理法で示すといいのか？
$ ac|bcならば$ a|b
定義に基づいて計算すればおけ
$ \lbrack a_1, a_2, a_3\rbrack bが$ a_1 b, a_2b, a_3bの公倍数であることはわかるので
これよりも小さい公倍数$ d' < \lbrack a_1, a_2, a_3\rbrack bが存在したら？
公倍数になるためには、最低限$ bの倍数である必要がある。
ということは、$ d' = d'' bということになる。
$ d'' < \lbrack a_1, a_2, a_3 \rbrack
いま、$ d''bは$ a_1b, a_2b, a_3bの公倍数だが、問1.2の内容から
一見図を書くと、確かに存在しそうに見える...が、これはどうやって証明すればいいんだろう
$ aに対して$ qbと$ (q+1)bの間に収まることを言う？
一応、背理法で解く方法はある（けど、当時の自分は思いついていなかった） 背理法と数学的帰納法を組み合わせて、
$ aがどの区間$ \lbrack qb, (q+1)b )にも存在しない
区間$ \lbrack qb, (q+1)b )は$ \Zの分割
を示せたら、$ a \in \Zであることと矛盾。
負の場合も一括で示せるから、こっちの方がパッパと済むけど、割り算の本質は現れない
でも、ここから解いてもこの問題の難しさは変わっていないような....。
むむむ
どこに着目すればよかったか
割り算の方法
or 最も簡単な場合について考える（$ 0 \leq a < bのときは、確かに満足する整数$ q, rが存在する）
なので、そこから数学的帰納法でどんどん$ aを大きい方へ繋げていって定理を証明すればいい 負の場合は適当に
$ r = 0のときとそうでない時とで少し扱いが変わる
負の数における余りがどうなっているかにも注目したい
余りの観点からこの問題を解いてみる。
余りを使うと$ x \not | \; yであるような$ yを簡単に表せるようになり、捉えやすくなる。
公倍数$ mは最小公倍数$ lの倍数である。
$ l \not | \; mである時と仮定する。
$ a_i| l, a_i | m
先に示した除法の定理を使うと、$ mの倍数関係を簡単に書き下せて
ある余り$ 0 < r < lが存在して$ r + ql = m
左辺は$ rのせいで$ a_iで割れない
割れたとしたら、$ lの最小性に反する。
従って、$ mも$ a_iで割れない。
これは$ mが公倍数であることと矛盾
$ (a, b) = (b, r)
$ (a, b)は$ b,rの最大公約数か？
公約数であることをまず示す。
$ a - bq = r
右辺は$ a, bの最大公約数$ (a, b)で割れる。 従って、$ rは$ (a, b)で整除される。
$ bも$ (a,b)で整除される。
従って、$ (a, b)は$ r, bの最大公約数
最大性？
仮にこれより大きい数$ d > (a, b)で$ b, rが割れたとして
$ a = bq + r
$ aは$ dで割れて、$ bも$ dで割れることになるので
$ dは$ a, bの公約数。
しかし、これは$ (a,b)の最大性に反するため矛盾
従って、$ (a,b)は最大公約数である。
と言いたいところだが、実際には
一つ目の$ (a,b)が公約数であることをまず示す。 における「最大公約数の最大性」を
$ (a, b)\leq (b, r)
によって表現し、
$ (b, r) \leq (a, b)を示しにかかるために
$ a, bの公約数の一つに$ (b, r)があることを示しにかかればすぐ済む。
ここあたりの議論に$ x \leq y \land y\leq x \Rightarrow x = yの論法がよく出てくるのは
$ O(\log a)（$ a > b）回の計算で済む。
$ r \leq a/2であることを示しにかかれば良い。
問1.10の計算問題を追いかけていれば、原理はすぐわかる
これは、$ (a,b)を表式として表すのにすごく便利
$ (a, b)の倍数関係を調べるのにすごく役に立つ。
WA.icon 定理 1.8
(1)の証明に苦戦
実際には、最大性・最小性を不等式として表して$ =に持っていけば簡単に解ける
(2)は、定理1.7を拡張すればよい
拡張ユークリッドの互除法の使い方がよくわかる問題
$ cdを解析するために、$ d = ax + byを使うとよい
AC.icon 問1.12 最大公約数のスカラー倍
けっこうしんどかった
定義として考えると、最大性・最小性は不等式として捉えるのが自然
AC.icon 問1.13 最小公倍数の分解
AC.icon 問1.14 互いに素な自然数と整除
問1.11の内容をすぐ再利用できる
これのおかげで整除が扱いやすくなってくるappbird.icon
$ dと$ a_iの関係を表式として表せるので、それを用いて倍数を解析する。 計算結果が$ (a, b) = 1になることは、基本的に
素因数分解
ユークリッドの互除法を適用した後の結果
としてでしか理解しづらい。
ので、拡張ユークリッドの互除法によって$ (a, b)の倍数関連を$ a, bの倍数関連を結びつけて理解するのが手っ取り早い。
目的
$ b = cをどう示したらいいんだろうか
$ b | c, c | bを示すか？
一番簡単に示せるのはこっちかな...。
$ b - c = 0を示すか？
でも、減算をどう絡ませるかが謎。
色々考えられる。
互いに素の条件は既約分数であることを意味してるんだろうな〜
分数が整数になることは、通分することで一つの値が割り切れることに帰着したい。
$ \lbrack b, c \rbrack \; | \; ab' + c'd
少なくとも、
$ b | ab' + c'd
$ c | ab' + c'd
$ b'x + c'y = 1
最小公倍数と今の現状をどう絡ませるかが謎だなあappbird.icon
2/3 + 1/3
粒度が揃っていないと、そもそも整数に揃わない
$ b, cについて具体例を当てはめて調べてみる
$ 1/b + 2/cだとどう？
$ bc|1c+2b
左辺に複数入ってるのが扱いにくいので、
$ b | 1c+2b
$ b|2bなので、$ b|1cで割れなきゃいけない
$ bと$ 1は互いに素だから....
定理1.10から、$ b|cで割れる！
$ c|1c+2b
同じく、定理1.10から、$ c|bで割れる！
よって、$ b = c
これだ
どう解けば短時間で解決したか？
$ b | c, c | bを示す方向に目を向けていたのはよかった。
一部分だけ具体例当てはめて考えればよかったのかもなあ
具体例で当てはめすぎると逆に本質が見えなくなる。
一部を固定して考える
$ bc|???型を扱いにくいと認識していた
それを、$ +が原因だと認識していたが、その$ +を避けて解こうとしていたのが原因
$ +をなくすために立ち回ればよかった
$ bc|???から、$ b|???かつ$ c|???に結びつければ$ +を消すことができていた。
困難（$ +）を消すためにはどうすれば良いか？ということに注力するべきだった？
最大値が等しいことの証明には不等号を使って対応できる
やっと結びついた...！！appbird.icon
$ p > 1ね
改めて考えると「持たない」って定義難しいな あんまり情報がなさそうに見えるけど
$ \sqrt{100} = 10まで調べればいいね
$ nのときに消すのは、$ n^2以上の数だけでいい
$ nm \;(m < n)はすでに消えてる
$ p\ |\ qならば$ p = q
$ p\ |\ qの定義$ \exists c; cp = qに戻って、素数の定義と照らし合わせる。
問1.20 二つの素数で整除できる時
$ p\ |\ a, q\ |\ aならば$ pq\ |\ a
定義に戻る。
$ a = pc_1 = qc_2と表せることができる
$ c_1は$ qで整除できることを示せたらOK
問 1.21
んん？pを素数とした時にp|ab --> p|a or p|bであることをどう示せばいいんだろう
背理法....ダメそう。
$ aも$ bも$ pで割り切れなかったら、この式に矛盾する
ほんと？
$ a, bの因数$ p_1, p_2によって$ pで構成されていた場合は...？
でもそれは素数じゃないもんね
これは一般論か？
ああ、$ 1 \leq p_1, p_2 < pとした上で、
$ p_1\ |\ a, p_2\ |\ bの条件がついていたら、$ p_1, p_2 = 1しかないって言えりゃいいのか
「a, bの間に素数pがまたがるようなことがない」....のが本質だけど、それをどう整数の関係で言い表せばいいのか
数pがまたがるってどういう状況だろう？